#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
const int N = 1e3 + 10;
int f[N][N];
int n, m;
int dist[N];
bool st[N];
int dj()
{
	memset(dist, 0x3f, sizeof dist);
	memset(st, 0, sizeof st);

	dist[1] = 0;

	for (int i = 1;i <= n;i++)
	{
		int a = 0;
		for (int j = 1;j <= n;j++)
		{
			if (!st[j] && dist[j] < dist[a]) a = j;
		}
		st[a] = true;

		for (int b = 1;b <= n;b++)
		{
			int c = f[a][b];
			if (c == 0x3f3f3f3f) continue;
			if (dist[a] + c < dist[b])
			{
				dist[b] = dist[a] + c;
			}
		}
	}
	int ret = 0;
	for (int i = 1;i <= n;i++) ret += dist[i];
	return ret;
}
int main()
{
	cin >> n >> m;
	memset(f, 0x3f, sizeof f);//用这个表存的时候必须把无效的位置都给成无穷大
	for (int i = 1;i <= m;i++)
	{
		int u = 0, v = 0, w = 0;
		cin >> u >> v >> w;
		f[u][v] = min(f[u][v], w);//别忘了重边
	}
	int ret = dj();
	for (int i = 1;i <= n;i++)
	{
		for (int j = i+1;j <= n;j++)
		{
			swap(f[i][j], f[j][i]);
		}
	}
	int ret1 = ret + dj();
	cout << ret1 << endl;
	return 0;
}